#include <iostream>
using namespace std;

void Divide(int arr[], int Lift, int Right);
void Merger(int arr[], int Lift, int mid, int Right);

void Divide(int arr[], int Lift, int Right)
{
	if (Lift >= Right) {
		return;
	}
	int mid = (Lift + Right) / 2;
	Divide(arr, Lift, mid);
	Divide(arr, mid + 1, Right);
	Merger(arr, Lift, mid, Right);

}
void Merger(int arr[], int Lift, int mid, int Right)
{
	int p1, p2, i, j;
	i = 0;
	p1 = Lift;
	p2 = mid+1;
	int *p = new int[10];
	while (p1 <= mid && p2 <= Right) {
		p[i++] = arr[p1] < arr[p2] ? arr[p1++] : arr[p2++];
	}
	while (p1 <= mid) {
		p[i++] = arr[p1++];
	}
	while (p2 <= Right) {
		p[i++] = arr[p2++];
	}
	for (i = 0, j = Lift; j <= Right; i++, j++) {
		arr[j] = p[i];
	}
	delete []p;
}


int main() {
	int arr[10] = { 11,8,9,6,7,6,2,7,5,9 };
	Divide(arr, 0, 9);
	for (int i = 0; i < 10; i++) {
		cout << arr[i] << endl;
	}
	system("pause");
	return 0;
}











